#include "vm/frame.h"
#include "vm/swap.h"
#include "vm/page.h"

#include "threads/palloc.h"
#include "threads/thread.h"
#include "threads/synch.h"

static struct list frame_list;

/* try to solve some sync problems */
//static struct lock frame_list_lock;
static struct semaphore mutex;


uint32_t frame_list_length;
static int full;

void frame_table_init(void) {
	size_t user_page_cnt; /* palloc.c */
	frame_list_length = user_page_cnt;
	list_init (&frame_list);
//	lock_init(&frame_list_lock);
	sema_init(&mutex, 1);
	full = false;
}

/* this function is just like a normal palloc */
void* frame_get(bool zeroflag,void* upage){
	/* sync */
//	lock_acquire(&frame_list_lock);

	sema_down(&mutex);

	void *kpage = palloc_get_page (zeroflag?PAL_USER | PAL_ZERO:PAL_USER );
	/* No pages are available. */
	if (kpage == NULL){
		/* some frame should be swaped */
		full = 1;
		kpage = evict(upage, thread_current());
//		lock_release(&frame_list_lock);
		sema_up(&mutex);
		return kpage;
	}

	else {
		/* add new page & frame into frame table */
		struct frame* f;
		f = (struct frame *) malloc (sizeof(struct frame));
		f->recent = 0;
		f->paddr = kpage;
		f->upage = upage;
		f->owner = thread_current();
		list_push_front(&frame_list, &f->elem);
	}
//	lock_release (&frame_list_lock);
	sema_up(&mutex);
	return kpage;
}

/* L:free a frame, frame table entry & page must both be freed. */
void frame_free (void *kpage){
	struct list *l = &frame_list;
	struct list_elem *e;
	struct frame *f = NULL;

//	lock_acquire(&frame_list_lock);
	sema_down(&mutex);
	for(e = list_begin(l); e != list_end(l); e = list_next(e)) {
		f = list_entry(e, struct frame, elem);
		if(kpage == f->paddr) {
			palloc_free_page(kpage);
			list_remove (&f->elem);
			break;
		}
	}
//	lock_release (&frame_list_lock);
	sema_up(&mutex);
	ASSERT(0);
}

struct frame* frame_find (void *kpage)
{

//	lock_acquire(&frame_list_lock);
	sema_down(&mutex);

	struct list *l = &frame_list;
	struct list_elem *e;
	struct frame *f = NULL;


	for(e=list_begin(l); e!=list_end(l); e=list_next(e)) {
		f = list_entry(e, struct frame, elem);
		if(kpage==f->paddr) {
//			lock_release (&frame_list_lock);
			sema_up(&mutex);
			return f;
        }
	}

//	lock_release (&frame_list_lock);
	sema_up(&mutex);
	return NULL;
}

bool frame_table_full(void) {
//	lock_acquire(&frame_list_lock);
	sema_down(&mutex);
	size_t s=list_size(&frame_list);
//	lock_release(&frame_list_lock);
	sema_up(&mutex);
	return s;
}

// Recent changes in the value over time
void changerec(void)
{
	if(full) {
	  struct list_elem *e;
	  struct frame* fp;
	  for (e = list_begin (&frame_list); e != list_end (&frame_list); e = list_next (e)) {
        fp = list_entry (e, struct frame, elem);
        if(fp->owner->pagedir != NULL) {
        	if(pagedir_is_accessed (fp->owner->pagedir, fp->upage)) {
        		pagedir_set_accessed (fp->owner->pagedir, fp->upage, false);
        		fp->recent=0;
        	}

        	else {
        		fp->recent++;
        	}
        }
	  }
	}
}

// Use Least Recently Used page replacement
struct frame* LRU(void)
{
//	lock_acquire(&frame_list_lock);
//	sema_down(&mutex);
    struct list_elem *e;
    struct frame* fp;
    struct frame* tar;
    int max =- 1;
    for(e=list_begin(&frame_list); e!=list_end(&frame_list); e=list_next(e)) {
		fp=list_entry (e, struct frame, elem);
		if(max<fp->recent) {
			max=fp->recent;
			tar=fp;
		}
	}
	tar->recent=0;
//	sema_up(&mutex);
//	lock_release(&frame_list_lock);

    return tar;
}
